- 173 - ГЛАВА 6 (Андрэ Ла Мот) Т Р Е Т Ь Е И З М Е Р Е Н И Е ------------------------------- Последние достижения в области электроники и программирования приблизили наши фантазии о техмерных видеоиграх к осязаемой реальности. Разработчики игр сегодня могут создать техмерные игры для недорогого ПК, позволяющие игрокам получить ощущения, всего несколько лет назад казавшиеся недоступными. Говоря по правде, и в прошлом были техмерные имитаторы полетов и несколько пространственных игр. Но все они были очень медленными и нуждались в мощных компьютерах. Естественно, это резко сужало круг потенциальных игроков. Все эти ограничения заставляли программистов искать пути создания нетрадиционных методов рендеринга. Эти новые способы были очень просты и имели производительность, еще пару лет назад считавшуюся невозможной. В данной главе мы сначала обсудим традиционные методы рендеринга для ПК, а затем погрузимся в технику, называемую "отсечение лучей".[Пожалуйста, не путайте с отсечением объектов! (прим.ред.)] Этот метод осуществляет рендеринг со скоростью, близкой к световой... Из этой главы вы узнаете: - Что такое трехмерное пространство; - 174 - - Как изображаются точки, многоугольники и объекты в трехмерном пространстве; - Масштабирование, трансляция и повороты в трехмерном пространстве; - Проекции; - Геометрическое моделирование; - Алгоритм удаления невидимой поверхности; - Алгоритм художника; - Алгоритм, использующий Z-буфер; - Что такое текстуры; - Метод трассировки лучей; - Алгоритм отсечения лучей; - Реализация алгоритма отсечения лучей; - Усовершенствование алгоритма отсечения лучей; - Освещение, затемнение и цветовая палитра. Мы начнем наш урок с основных концепций трехмерного пространства, чтобы кое-что вспомнить и понять. Затем мы бросимся вперед, чтобы узнать как создаются игры типа Wolfenstein, DOOM и Terminator Rampage! ЧТО ТАКОЕ ТРЕХМЕРНОЕ ПРОСТРАНСТВО Трехмерное пространство... Звучит как строка из фантастического рассказа... Ну очень похоже. Трехмерное пространство - это просто расширение двухмерной плоскости. Надо сразу отметить, что рендеринг трехмерной графики весьма сложен. Вообще же сложность рендеринга экспоненциально возрастает с добавлением новых измерений и происходит это оттого, что и сами образы при этом усложняются. Наша задача заключается в том, чтобы понять, как работать с новым измерением. Мы должны все это изучить. Говоря языком математики, любая точка в трехмерном пространстве описывается с помощью уникального набора трех координат: x, y и z. Как мы уже обсуждали ранее, обычно экран представляется плоскостью X и Y, а координата z перпендикулярна экрану. В отличие от плоскости, где x-координата горизонтальна, а y-координата вертикальна, трехмерные системы координат бывают двух типов: - Левосторонняя система координат; - Правосторонняя система координат. - 175 - Рис.6.1. Трехмерная система координат. На рис.6.1 показано представление обоих способов отображения трехмерных систем. В дальнейшем для всех наших рассуждений, примеров и программ мы будем использовать только правостороннюю систему координат. На то есть две причины: - Правосторонняя система удобней в работе, поскольку в ней проще выполняется визуализация; - Правосторонняя система распространена как стандарт. Конечно, вы можете сказать, что экран компьютера - это плоскость, и мы не можем преобразовывать трехмерные образы в двух измерениях. Верно. Вы абсолютно правы. Но у нас есть возможность отобразить их на плоскость. Мы даже можем видеть "тени" объектов. И сделать это позволит проекция. При этом модель выглядит на двухмерном экране так, что у зрителей возникает полное ощущение объемности. Такие игры как DOOM и Wolfenstein трехмерны только в нашем восприятии. Можно сказать, что в них смоделирован особый случай трехмерного пространства, образы которого можно обрабатывать гораздо проще и быстрее. В любом случае, мы еще к этому вернемся, а теперь давайте поговорим об основных понятиях трехмерного пространства. ТОЧКИ, ЛИНИИ, МНОГОУГОЛЬНИКИ И ОБЪЕКТЫ В ТРЕХМЕРНОМ ПРОСТРАНСТВЕ Как мы уже видели, точка в трехмерном пространстве имеет три координаты (x,y,z). Этой информации достаточно, чтобы ее однозначно определить в пространстве. - 176 - Будет логично, если следующим объектом, который мы определим, станет линия. Линией называют отрезок, соединяющий две точки в трехмерном пространстве. Мы можем даже написать структуры данных, определяющие точку и линию. Листинг 6.1. Определение точки и линии в трехмерном пространстве. ------------------------------------------------------------------------------ // структура, определяющая точку в трехмерном пространстве typedef struct point_typ { float x,y,z // координаты точки } point, *point_ptr; // структура, описывающая линию в трехмерном пространстве typedef struct line_typ { point start, end; // линия задается двумя точками } line, *line_ptr; ____________________________________________________________________________ Используя структуры из Листинга 6.1, давайте определим линию, которая начинается в точке (0,0,0) и идет в точку (100,200,300) line linel; linel.start.x = 0; linel.start.y = 0; linel.start.z = 0; linel.end.x = 100; linel.end.y = 200; linel.end.z = 300; Теперь мы имеем описание линии. Если мы захотим, то сможем создать трехмерный мир, состоящий из линий и точек, но это будет скучным и тоскливым занятием. Нам нужен больший уровень абстракции для моделирования объектов, и для этого нам пригодятся многоугольники. Как вы поняли из 4-й главы, многоугольник - это множество вершин, соединенных отрезками прямых. Вершины определяют границы многоугольника. В трехмерном пространстве многоугольники очень похожи на своих двухмерных собратьев. Попробуем определить трехмерный треугольник. Он может выглядеть так, как это изображено на рис. 6.2. - 177 - Рис.6.2. Трехмерный треугольник. Если вы можете видеть, на листе бумаги весьма несложно представить трехмерный объект. Мы будем использовать для описания "диагональный вид". Позже мы к этому еще вернемся, а сейчас важно понять идею. Описать многоугольник довольно просто: мы применим старое определение многоугольника и просто добавим к нему несколько атрибутов для создания новой законченной структуры. В Листинге 6.2 показана такая структура. Листинг 6.2. Определение трехмерного многоугольника. ---------------------------------------------------------------------------- // структура, описывающая многоугольник typedef struct polygon_typ { int num_vertices; // число вершин vertices[MAX_VERTICES]; // координаты вершин int color; // цвет многоугольника } polygon, polygon_ptr; ____________________________________________________________________________ Как можно заметить, в структуре описаны вершины и цвета. Эти составляющие необходимы для правильного отображения. Теперь, когда у нас есть структура, описывающая многоугольник, следующим шагом будет определение объекта на основе многоугольников. На рис.6.3 продемонстрирован один из таких объектов. Теперь мы можем добавить еще один уровень к нашему описанию. Объект - это набор многоугольников. Создадим структуру, которая бы поддерживала эту концепцию: - 178 - Рис.6.3.Трехмерный объект на основе многоугольников. Листинг 6.3. Описание трехмерного объекта на основе многоугольников. ---------------------------------------------------------------------------- // структура, описывающая объект typedef struct object_typ { int num_faces; // число граней polygon faces[MAX_FACES]; // грани, представленные многоугольниками float xo,yo,zo; // координаты объекта в пространстве int visible; // виден ли объект на экране? } object, *object_ptr; ____________________________________________________________________________ Структура данных в Листинге 6.3 описывает оьъект, который образован множеством многоугольников или поверхностей. Используя эти структуры данных и определения, мы можем создать несколько трехмерных объектов: космический корабль, планету и окружающее космическое пространство. Чтобы поместить объекты в трехмерное пространство, мы должны знать их пространственное расположение. То есть мы должны определить значения xo, yo, zo для каждого предмета. Так же, как в сдлучае с двухмерными объектами (которые мы уже обсуждали в 4-й главе), пространственные объекты мы будем определять в собственных локальных системах координат (0,0,0). Затем, когда мы будем перемещать объект, мы его просто переведем в конечную позицию. - 179 - Рис.6.4. Куб, созданный относительно точки (2,2,2). Для наших структур это будет точка (xo,yo,zo). Решением этой задачи будет простой перенос каждой из точек объекта, так же, как мы это делали для двухмерных объектов. Мы можем проверить этот метод и для объемных фигур. Например, представим себе куб с вершиной в точке (2,2,2) (см.рис.6.4). Если мы посмотрим на куб, то увидим, что он состоит из 8 вершин и 6-ти поверхностей. Используя наши структуры данных, мы можем описать куб, как объект с 6-ю гранями. Проблема, возникающая в данном случае, состоит в том, что это не самый лучший способ описания объекта. Ведь любая поверхность ограничена четырьмя точками и каждая из этих точек является общей еще для двух поверхностей. Это значит, что описание избыточно. Возможно, более удачной окажется структура данных, содержащая список вершин. В этом случае избыточности не возникает. Однако при этом структура станет более общей и сложной, поскольку: - Мы должны будем иметь указатели либо индексы, или то и другое вместе для ссылки на вершины, необходимые для построения геометрической фигуры. Это увеличивает время распознавания данных объектов; - Наши структуры могут использовать заранее определенные массивы для хранения вершин и многоугольников. Это неэффективно использует память. Массивы должны быть одного размера, так как независимо от того, используем ли мы один элемент массива или весь массив, нам необходимо отводить место под максимальное число элементов. Эти факты надо принимать во внимание, когда создаете структуры для трехмерных объектов. Таким образом, для наших целей структуры данных из Листингов 6.2 и 6.3 являются наиболее простыми для работы. Если же вы хотите создать набор реальных трехмерных структур, то должны использовать другую тактику. - 180 - В общем случае представление двух- и трехмерных объектов сильно зависит от игры, которую вы пишете, от размера используемой памяти и т.д. (Наша цель сейчас - понять механизмы трехмерной графики и рендеринга, а не поиск наиболее эффективных способов представления данных в компьютере. Это зависит от используемых алгоритмов и структур данных.) Просуммируем все вышесказанное: - Трехмерные объекты состоят из вершин; - Эти вершины соединяются поверхностями или многоугольниками, которые задают границы объекта; - Объекты описываются относительно начала координат; - Существует много способов представления трехмерных объектов и вы должны выбрать тот, который устраивает вас по скорости и объему памяти. ПЕРЕМЕЩЕНИЯ, МАСШТАБИРОВАНИЕ И ПОВОРОТЫ В ТРЕХМЕРНОМ ПРОСТРАНСТВЕ Все объекты в видеоиграх представлены точками, линиями и геометрическими фигурами. Потому мы должны всегда производить их разбиение на исходные составляющие - точки. Только проделав это, мы можем их преобразовывать. Поскольку точки - это вершины объектов, то они могут рассматриваться вообще отдельно от объекта, но при этом представлять его в целом. Например, если мы хотим повернуть или переместить куб, то прежде чем выполнять данное преобразование, нам нужно разбить объект на многоугольники, а затем на точки. Понимая это, мы должны сосредоточить свое внимание на способах преобразования точек. Перемещение трехмерного объекта --------------------------------------- Для перемещения точки (x,y,z) на расстояние (dx,dy,dz) необходимо выполнить следующие операции: x=x+dx; y=y+dy; z=z+dz: Если мы хотим ипользовать эту матрицу, то должны представить точку в виде четырех компонентов (x,y,z,1). Матричное умножение будет выглядеть так: - 181 - │1 0 0 0│ │0 1 0 0│ [x' y' z' 1] = [x y z 1] │0 0 1 0│ │dx dy dz 1│ где dx, dy и dz - это перемещения по осям координат, а x', y' и z' - координаты точки после перемещения. Масштабирование трехмерного объекта ----------------------------------------- Следующая операция трансформации, которую должны уметь выполнять, это масштабирование. Изменение размеров трехмерного объекта похоже на двухмерное масштабирование. Здесь показано масштабирование точки (x,y,z) с коэффициентом S: x=x * S; y=y * S; z=z * S; Все очень просто. Только кажется, что трехмерная графика сложна для понимания. Для описания преобразований с помощью матриц мы опять должны представить точку в виде (x,y,z,1): │S 0 0 0│ │0 S 0 0│ [x' y' z' 1] = [x y z 1] │0 0 S 0│ │0 0 0 1│ Если вы решите масштабировать каждый из компонентов по-разному, то вам потребуются разные коэффициенты для каждого измерения: │Sx 0 0 0│ [x' y' z' 1] = [x y z 1] │0 Sy 0 0│ │0 0 Sz 0│ │0 0 0 1│ Это приведет к неоднородному масштабированию. Вращение трехмерного объекта ------------------------------------ Последняя трансформация, о которой мы поговорим - это вращение. Вращение трехмерного объекта аналогично двухмерной ротации, необходимо только добавить третье измерение. - 182 - Вращение, параллельное оси X ------------------------------ Следующая матрица преобразований вращает точку (x,y,z) параллельно оси X: │1 0 0 0│ │0 cos r sin r 0│ [x' y' z' 1] = [x y z 1] │0 -sin r cos r 0│ │0 0 0 1│ где r - угол вращения в радианах. Вращение, параллельное оси Y ----------------------------- Матрица преобразования, вращающая точку параллельно оси Y: │cos r 0 -sin r 0│ │0 1 0 0│ [x' y' z' 1] = [x y z 1] │sin r 0 cos r 0│ │0 0 0 1│ где r - угол вращения в радианах. Вращение, параллельное оси Z ----------------------------- Матрица преобразования, вращающая точку параллельно оси Z: │cos r sin r 0 0│ │-sin r cos r 0 0│ [x' y' z' 1] = [x y z 1] │0 0 1 0│ │0 0 0 1│ где r - угол вращения в радианах. Последнее слово о трехмерных трансформациях -------------------------------------------------- Подведем итог разговору о трансформациях трехмерных объектов. Реализовать эти трансформации не сложно. Это только часть возможных преобразований. Существует много вариаций и несколько совершенно новых типов - деформация и т.д. В общем, мы уже достаточно знаем, чтобы перейти к проекциям. ПРОЕКЦИИ Сейчас мы знаем, как изобразить трехмерный оьъект и как произвести операции перемещения, масштабирования и поворота этого объекта. Возникает вопрос: "А как мы можем рисовать трехмерные объекты на плоском экране?" Ответ прост: мы "проецируем" их на поверхность экрана. - 183 - Проекция трехмерных объектов на плоскость довольно проста и дает хорошие результаты. К сожалению, образы при этом не всегда выглядят реалистично. Ваши глаза имеют одну точку зрения, а, следовательно, образ будет похож на трехмерный, но не станет "по-настоящему" объемным. Замечание. --------------- Существуют специальные шлемы с дисплеями, дающие стереоскопический эффект. Эти шлемы используются в системах виртуальной реальности. Проблема, возникающая с их использованием, заключается в том, что параллакс или фокальная точка различна для каждого человека. Если шлем не отрегулирован и точка не подобрана, то зритель вскоре получит сильнейшую головную боль. ------------------ Тем не менее, мы будем использовать монитор для проецирования трехмерного образа на экран. Я хотел бы обсудить типы проекции, которые могут применяться с этой целью: параллельная, или ортогональная проекция и перспективная проекция. Рис.6.5 показывает диаграммы каждого типа проекций. Параллельная проекция проста в реализации, но образы не выглядят объемными. Они, скорее, похожи на обычные плоские картинки. Для реализации такой проекции достаточно убрать Рис.6.5. Два типа трехмерной проекции. - 184 - Рис.6.6. Дорога в никуда. Z-компонент каждой точки трехмерного объекта и затем нарисовать объект, как двухмерный. С другой стороны, перспективная проекция дает большее приближение и выглядит почти "трехмерно". Она имеет качество "длинной дороги". На рис.6.6 изображена такая "дорога". Перспективная проекция принимает во внимание Z-компонент и соответственно изменяет компоненты X и Y. Элементы, которые подвергаются "перспективному" преобразованию, должны: - Просто делиться или умножаться на Z-компонент; - Обладать дистанцией просмотра. Вскоре мы затронем детали проецирования, но сначала давайте поговорим об экране и его взаимоотношениях с координатами трехмерного пространства. Копирование на экран -------------------------- Создание настоящей трехмерной графической системы - довольно сложное дело. Этому посвящены целые книги (еще толще, чем та, которую вы держите в руках). В первом приближении нам нужны: - Кое-какие трехмерные объекты; - Объем просмотра; - Проекция на план (плоскость) просмотра. Мы можем быть спокойны относительно трехмерных объектов - мы определили многоугольники как множество вершин и построили на их основе объекты. А вот что касается объема просмотра и плана просмотра, то тут требуются некоторые разъяснения. - 185 - Рис.6.7. Взгляд на мир. Когда мы смотрим на трехмерный мир, то сами должны в нем где-то находиться и иметь направление просмотра. Рис.6.7 иллюстрирует эту мысль. Учитывая, что в реальном мире мы смотрим на объекты с определенной точки и в определенном направлении, мы можем их построить на экране, который и будет являться планом просмотра. Такой подход довольно сложен, поскольку требует выполнения множества преобразований для решения данной задачи в общем виде. Но поскольку мы программисты, нас не очень должно волновать общее решение задачи. Нам надо создавать игры, выглядящие как трехмерные. - Во-первых, мы делаем допущение, что центр экрана совпадает с центром системы координат. Рис.6.8 показывает, как она выглядит на экране; - Во-вторых, мы предполагаем, что игрок будет смотреть на экран вниз по оси Z (отрицательное неправление). Мы можем спроецировать одиночный пиксель в точку (0,0,0) на экран, используя параллельную проекцию, и увидеть точку в центре экрана. Рис.6.9 показывает разницу между параллельной и перспективной проекциями. Вы можете заметить, что центр проекции - это дистанция между игроком и планом просмотра (поверхностью экрана). Математика для проецирования трехмерных объектов на экран сказочно проста и мы ее реализуем за пару минут. Но пока поговорим о масштабировании. - 186 - Рис.6.8.Отображение правосторонней системы координат на экран. Рис.6.9. Два типа проекций на экран. - 187 - Масштабирование экрана ----------------------------- Поскольку в режиме 13h экран имеет размеры 320х200 точек, то возникает вопрос: "Как мы сможем увидеть вселенную размером 1000х1000 точек?" Есть много способов решения этой проблемы. Один из путей - это использование перспективной проекции. Когда мы удаляемся от объекта, он становится меньше. В некоторой точке вселенная размером 1000х1000 уменьшается настолько, что "влезает" в экран. Если вы используете параллельную проекцию, вам не удастся добиться такого результата. Чтобы сделать это, вы должны масштабировать экран и использовать его с другими размерами. Например, для получения экрана размером 1000х1000 мы должны сделать следующее. Чтобы нарисовать точку (x,y) на экране, где каждый из компонентов имеет диапазон измерения от 0 до 1000, мы производим преобразования x_screen = 320 * x / 1000; y_screen = 200 * y / 1000; где x_screen и y_screen будут истинными координатами пикселя на экране размером 320х200. Конечно, изменив таким образом масштаб экрана, вы не получите разрешения 1000х1000 точек. Разрешающая способность останется прежней - 320х200. Более того, некоторые точки будут изображены в одних и тех же местах. Например, точки с координатами 999 и 1000 сольются в одну, и вы не сможете их различить. Но это не столь важно, поскольку трехмерное изображение на основе многоугольников отличается от битовых изображений двухмерного мира. Математические основы параллельных проекций --------------------------------------------------- Математика, необходимая для произведения параллельной проекции, элементарна - вы просто убираете z-координату и рисуете каждую точку объекта по координатам (x,y). Вот и вся трансформация. Для примера возьмем точку (x,y,z). x_parallel = x y_parallel = y plot x,y Математические основы перспективной проекции ---------------------------------------------------- Произведение перспективной трансформации не многим отличается от параллельной проекции. Мы используем z-компонент для масштабирования координат x и y с целью "отдаления" точки от плана просмотра (поверхности экрана), и для придания объекту более реалистичного вида. - 188 - Рассмотрим эту операцию на примере: дана точка (x,y,z), удаленная от плана просмотра на расстояние D: x_perspective = D * x / z y_perspective = D * y / z Вот и все. Достаточно умножить каждый компонент на расстояние и разделить на значениеZ-координаты. Образ получается похожим на трехмерный. Объем просмотра -------------------------- Мы говорили об объектах и проекциях в трехмерном пространстве, но не упоминали об объеме просмотра. Это понятие подобно области отсечения для двухмерного мира (мы это обсуждали в 4-й главе "Механизмы трехмерной графики"). Так же как мы отсекаем объекты у границ экрана в двухмерных играх, мы должны проделывать это и с трехмерными объектами. Видимая часть пространства имеет шесть поверхностей и чем-то напоминает трехмерную трапецию или усеченную пирамиду (см.рис.6.10). Эта область иногда называется еще телесным углом просмотра. Объекты, попадающие в объем просмотра, визуализируются; объекты, выходящие за пределы объема просмотра, отсекаются. Рис.6.10. Объем просмотра. В общем случае, нам нужно отсечь каждый объект или его часть, выходящую за границы телесного угла просмотра. Поскольку отсекаемые фрагменты при перспективной проекции становятся не видны, тои нет необходимости выполнять их рендеринг. -189 - Наиболее важны ближняя и дальняя плоскости отсечения (рис.6.10). Когда объект подходит слишком близко к экрану, то он должен исчезать (он как-бы оказывается у вас за спиной), а когда он удаляется на слишком большое расстояние, то мы его тоже можем убрать, поскольку он просто превратится при рендеринге в точку. Я больше ничего не буду говорить про трехмерное отсечение - оно не потребуется для игр типа DOOM и Wolfenstein, но может пригодиться для создания различных "леталок" и "ездилок". Вы можете использовать ту же тактику, что и для двухмерного отсечения. Теперь нам надо познакомиться еще с одной вещью - моделированием цельных геометрических объектов. ГЕОМЕТРИЧЕСКОЕ МОДЕЛИРОВАНИЕ Геометрическое моделирование необходимо для придания играм большего реализма. Объекты, построенные компьютером при геометрическом моделировании, выглядят цельными. Посмотрите на рис.6.11, чтобы увидеть разницу между цельной и каркасной моделями. Рис.6.11. Каркасная и цельная геометрическая модели. Как видите, геометрическая модель выглядит более убедительно. Сегодня использование каркасных объектов уже нельзя назвать удовлетворительным решением. Теоретически создание цельных моделей ненамного сложнее, нежели каркасных. Мы можем использовать те же самые структуры данных, преобразования и проекции. Но когда мы пытаемся нармсовать цельный трехмерный объект, возникают определенные проблемы. Как вы понимаете, существуют еще и скрытые поверхности - те, которые не видны игроку (например, тыльная сторона рассматриваемого объекта) и которые не должны появляться на экране. Компьютер не понимает разницы между видимыми и невидимыми поверхностями. - 190 - Он нарисует их все. Чтобы избежать этого, мы должны найти способы удаления скрытых поверхностей. Сейчас мы об этом и поговорим. Удаление невидимых поверхностей --------------------------------------- Среди программистов, работающих в области компьютерной графики, техника удаления невидимых поверхностей считается "высшим пилотажем". Известно, что удаление невидимых поверхностей является сложной математической задачей. Существует довольно много алгоритмов для ее решения, но все они очень сложны в реализации и редко работают с приемлемой для видеоигр скоростью. Удаление невидимых поверхностей можно разделить на две фазы. Фаза 1. Прежде всего удаляются поверхности, которые никогда не будут видны с точки зрения наблюдателя. Для этого мы должны использовать точку пересечения между вектором наблюдения и вектором нормали к каждой из рассматриваемых плоскостей. Мы вычисляем это значение. Если значение угла меньше 90 градусов, то поверхность видна, если больше 90 гр. - нет, и она удаляется. Фаза 2. После того, как скрытые поверхности удалены, видимые плоскости должны быть окрашены. Вы должны быть уверены, что в течение этой фазы объекты будут выглядеть правильно. Рис.6.12. Проверка поверхности на видимость. Существует популярный Алгоритм Художника, который это хорошо умеет делать. Он работает, выполняя пять тестов для каждой видимой пары многоугольников (поверхностей) и затем создает последовательность их окраски от дальней части изображения к ближней. - 191 - Другая техника создания этой последовательности носит название Алгоритма Z-буфера. Он работает в пространстве образа на уровне пикселей. Он прост в реализации, но медленно работает и требует много памяти. Настоящие разработчики видеоигр никогда не используют эти алгоритмы в чистом виде. Мы должны создать свою систему, которая будет сочетать оба метода. Для этого детально рассмотрим каждый из них. Алгоритм Художника -------------------------- Алгоритм Художника - это один из тех алгоритмов, которые могут создавать ощущение реальности. Основная идея Алгоритма Художника состоит в сортировке поверхностей таким образом, что при рендеринге это выглядит корректно. Наиболее просто этот алгоритм может быть реализован, когда каждая поверхность параллельна плану просмотра (то есть перпендикулярна лучу зрения). В этом случае нам достаточно отсортировать поверхности в порядке уменьшения значения координаты Z. Зтем мы сначала нарисуем самую дальнюю поверхность, потом более близкую и т.д. Это достаточно специфичное условие, но и у него есть свои реализации. Проблемы начинают возникать, когда поверхность не параллельна плану просмотра. При этом все разбивается на куски и мы вязнем в выполняемых тестах. Это значит, что нам надо выполнить множество вычислений. Рис.6.13 показывает вид сверху вниз двух многоугольников в одном из самых неудачных случаев. Безразлично, как мы будем сортировать эти многоугольники - по минимуму, максимуму или среднему значению Z - мы всегда получим неверный результат. Чтобы этого избежать, мы должны проделать 5 тестов для каждой пары многоугольников. Рис.6.13. Неудачное расположение двух многоугольников. - 192 - Рис.6.14.Тест на совпадение X-координат. Тесты выполняются только в том случае, если значения Z для двух многоугольников совпадают. Иначе, они могут рисоваться в любой последовательности. Алгоритм Художника, Тест 1 --------------------------------- Имеются ли общие значения X-координат для многоугольника 1 и многоугольника 2, как это изображено на рис.6.14? - Если нет, то с этой парой многоугольников все в порядке. Последовательность их рисования не играет роли, поскольку они не закрывают друг друга; - Если да, то перейти к Тесту 2. Алгоритм Художника, Тест 2 --------------------------------- Имеются ли общие значения Y-координат для многоугольника 1 и многоугольника 2, как это показано на рис.6.15? - Если нет, то их можно рисовать также в любом порядке; - Если да, то выполнить Тесты 3 и 4. - 193 - Рис.6.15. Тест на совпадение Y-координат. Рис.6.16. Плоскость отсечения. - 194 - Алгоритм Художника, Тесты 3 и 4 -------------------------------------- Тесты 3 и 4 похожи, поскольку оба они работают с отсекающими плоскостями. Чтобы понять тест, мысленно продолжите грани многоугольника в бесконечность в обоих направлениях, создавая плоскость. Это плоскость отсечения. Посмотрите на рис.6.16. Чтобы выполнить этот тест, создайте плоскость отсечения для первого многоугольника и проверьте многоугольник 2, а затем проделайте все то же самое, но наоборот. - Если ни одна из построенных плоскостей отсечения не пересекает другой многоугольник, то они могут быть корректно отрисованы; - Иначе перейти к Тесту 5. Алгоритм Художника, Тест 5 ---------------------------------- К этому моменту мы уже практически полностью уверены в том, что многоугольники перекрывают друг друга. Единственное, что осталось проверить - форму многоугольников. Возможно, что благодаря наличию углублений перекрываются не сами многоугольники, а только описывающие их прямоугольники. Такая ситуация показана на рис.6.17. Рис.6.17. Проверка некорректного пересечения. Обработка такой ситуации настолько сложна, что в этом случае не существует каких-либо общих рекомендаций. - 195 - Время выполнения Алгоритма Художника --------------------------------------- Алгоритм Художника хорошо, но, к сожалению, медленно работает. В худшем случае, количество операций примерно равно 0(n2), где n - количество многоугольников. Алгоритм Z-буфера -------------------------- Поскольку скорость и объем памяти ПК постоянно увеличивается, на смену Алгоритму Художника пришел Алгоритм Z-буфера. Этот алгоритм более прост в реализации, чем Алгоритм Художника. (Сегодня большинство высокопроизводительных графических систем и графических станций имеют аппаратную реализацию этого алгоритма, что избавляет от необходимости решать проблему удаления невидимых поверхностей самостоятельно). Реализация Алгоритма Z-буфера проста. Все, что для этого нужно - сам Z-буфер, который имеет такой же объем, как и видеобуфер. В нашем случае это будет матрица целых чисел размером 320х200. Затем мы заполняем ее значениями Z-координат многоугольников, следуя таким правилам: 1. Для данного множества трехмерных поверхностей вычисляем их проекции на план просмотра, иначе - на экран. Чтобы нарисовать трехмерный многоугольник на плоском экране, мы должны спроецировать его на план просмотра, используя один из двух видов проекции, которые мы обсуждали ранее. После проецирования многоугольник будет обладать множеством вершин, являющихся точками на плоскости. Потом мы заполним многоугольник, используя эти точки для создания граней. 2. Определяем X- и Y-компоненты для каждой точки (необходимо помнить, что может быть сколько угодно точек с одинаковыми значениями X- и Y-координат и различными значениями Z.) 3. Затем используем уравнение плоскости для плоскости, общей с многоугольником, решая его относительно компонента Z для каждой пары X- и Y-координат, после чего вычисляем значение Z для всех точек в границах многоугольника. 4. Записываем значение Z и цвет для каждой точки Z-буфера. 5. Затем мы смотрим, какая из точек будет нарисована на экране. Чтобы сделать это, найдем точку со значением Z-координаты, ближайшей к плану просмотра. 6. Рисуем пиксель с цветом данной точки. - 196 - Уравнение плоскости ----------------------- Я говорил, что мы можем использовать уравнение плоскости для многоугольника, для нахождения значения Z-компонента каждого из пикселей внутри преобразуемого прямоугольника. Вот это уравнение. Дано: Точка (x,y) и вектор нормали к многоугольнику Nz Z = ----------------------- 1 - Nx х x - Ny x y Использование уравнения плоскости для вершин многоугольника ---------------------------------------------------------------- А каким образом мы можем составить уравнение плоскости, зная только вершины многоугольника? Очень просто: так как все вершины прямоугольника принадлежат одной плоскости, мы можем взять две смежные вершины и построить к ним вектор нормали. Рис.6.18 показывает, как это сделать. Вектор нормали может быть использован в уравнении плоскости для вычисления Z-компонента. Рис.6.18. Вычисление вектора нормали. Имея вектор нормали к многоугольнику, уравнение плоскости находит Z-компонент для любой точки (x,y). При этом заданы: искомая точка (x,y) и вектор нормали к многоугольнику : Nz Z = -------------------- 1 - Nx x x - Ny x y - 197 - Соотношение пространства образов и пространства объектов -------------------------------------------------------------- Алгоритм Z-буфера хорошо работает и может быть легко реализован. Единственная проблема состоит в том, что он работает на уровне пикселей и является алгоритмом обработки образа. Это значит, что он не рассматривает геометрических свойств объекта. Это требует наличия некоторого гибридного алгоритма для использования в специальных случаях. Такой алгоритм должен учитывать геометрические свойства объекта перед простым удалением невидимых поверхностей. Теперь давайте поговорим о том, как придать поверхности наших трехмерных объектов большую реалистичность. Трассировка лучей -------------------------- Трассировка лучей - это метод, применяемый для создания реалистичных образов на компьютере, используя полные модели трехмерного мира. Трассировка лучей решает множество проблем. Этот алгоритм может выполнять следующие действия: - Удаление невидимых поверхностей; - Перемещение; - Отражение; - Рассеяние; - Окружающее освещение; - Точечное освещение; - Наложение теней. Изначально этот алгоритм разрабатывался для решения проблемы удаления невидимых поверхностей. Трассировка лучей создает образ, исходя из тех же заклнов, что и наше зрение. На рис.6.19 изображено некоторое пространство, которое может быть просчитано с помощью алгоритма трассировки лучей. Вы видите несколько объектов: источник света, наблюдателя и план наблюдения. Чтобы воспользоваться трассировкой лучей для создания натуральных образов, нам придется использовать миллиарды световых лучей из источника света, а затем рассматривать каждый из них, надеясь, что он попадет в план наблюдения и примет участие в создании образа. Возникает вопрос - а зачем трассировать каждый возможный луч? На самом деле, нас интересуют только те лучи, которые достигают плана просмотра. Запомнив это, давайте попробуем трассировать лучи в обратном направлении. Проследим движение лучей для каждого из пикселей на экране, а затем посмотрим, где эти лучи пересекаются с планом просмотра. Отметив пересечение, мы останавливаемся и окрашиваем соответствующий пиксель в нужный цвет. Это называется первичной трассировкой лучей. - 198 - Рис.6.19.Общий вид панорамы для трассировки лучей. Данная техника позволяет создавать трехмерные образы, но при этом не видны такие эффекты, как тени, рефракция и рефлексия. Чтобы воссоздать перечисленные эффекты, мы должны принять в рассмотрение специальные вторичные лучи, которые исходят из точек пересечения. Это все делается рекурсивно до достижения некоторого уровня детализации. Затем полученные по всем лучам результаты складываются и соответствующему пикселю присваивается вычисленный цвет. Трассировка лучей - это один из наиболее насыщенных вычислениями методов расчета трехмерных изображений, но зато и результаты получаются впечатляющими. Это только одна проблема: для решения этой задачи в реальном времени не хватает мощности даже самого быстродействующего компьютера. Потому нам придется учесть данное обстоятельство и применить идею трассировки лучей для создания другого метода. Он будет более ограничен, но позволит нормально работать с трехмерными мирами на обычном ПК. Исходя из этого, мы попробуем реализовать упрощенный вариант трассировки лучей, используя только первичные лучи для генерации изображения. С последующими оптимизациями возможно достижение достаточно высокой производительности. Если вам интересно узнать, как это можно сделать, то стоит продолжить чтение нашей книги. - 199 - Отсечение лучей ------------------------ Для создания реалистичного трехмерного изображения в играх используется техника, называемая отсечением лучей. Применяя эту технику, надо придерживаться некоторых правил, связанных с тем, что алгоритм отсечения лучей - это, в сущности, упрощение алгоритма трассировки, в котором все же осталось множество вычислительных проблем. Поэтому данный алгоритм применим только для наиболее простой геометрии создаваемых миров. В общем случае, отсечение лучей не будет работать, если вы решите сделать трехмерный имитатор полетов или попытаетесь смоделировать реальное пространство. Но в играх, где действие происходит в мире, нарисованном с помощью перпендикулярных линий, этот алгоритм работает изумительно. Для создания DOOM-образных миров применяется несколько иная техника, но и она базируется на этом же алгоритме. Я написал маленькую демонстрационную программку, в основе которой лежит алгоритм отсечения лучей. Она позволит нам "погулять" по трехмерному миру, состоящему из кубов. Весь этот мир на самом деле является двухмерной матрицей, считываемой из обычного ASCII-файла. Я решил использовать графическую библиотеку Microsoft, поскольку сейчас меня не волнует вопрос быстродействия. Я решил, что вам надо иметь перед глазами двух- и трехмерные картинки, поэтому использовал режим высокого разрешения и соответствующие библиотеки. Это дает лучшие ощущения для понимания механизма процесса. Следующие страницы будут насыщены деталями и техническими подробностями. Отсечение лучей теоретически просто, но практическая реализация весьма сложна. Это связано с тем, что приходится принимать во внимание кучу мелких деталей. Эти детали очень важны. Я покажу вам очень простую программу отсечения лучей, но основной задачей будет понять принцип ее работы. Поскольку здесь я использовал библиотеки поддержки математических операций с плавающей запятой, то программа работает довольно медленно. Когда вы ее оттранслируете и запустите, то увидите три окна вывода. Они показаны на рис. 6.20. Изображение в левом углу экрана представляет собой плоскую карту трехмерного мира, который является матрицей размером 64х64х64. Полная трехмерная модель из этой матрицы создается посредством отсечения лучей. Как это получается, изображено в правой части экрана. Для перемещения используйте цифровую панель клавиатуры. Чтобы выйти из программы, нажмите клавишу Q. В процессе работы с программой у вас должно появиться представление о строении трехмерного образа: он построен из вертикальных полос. Эти полосы образуются в процессе поворота луча в точке просмотра на определенный угол. - 200 - Рис.6.20.Изображение экрана вывода программы RAY.EXE. Рис.6.21.Образ, полученный отсечением лучей. - 201 - Идею алгоритма отсечения лучей можно представить так: вообразите, что вы стоите в пустой комнате и смотрите вперед. Все, что вы наблюдаете, это стены впереди и по обе стороны от вас. Образ, который вы видите, складывается из лучей, отразившихся от стен и попавших в ваши глаза. Но при отсечении лучей происходит не отражение от стен, а просто отсечение лишних лучей. На рис.6.21 показан образ, полученный таким методом. Как и в системах лазерного сканирования, мы также как-бы сканируем область вокруг нас и строим образ на основе полученных результатов. То, что мы в итоге получим, будет зависеть от поля просмотра. Это поле является той "порцией" информации, которую мы можем увидеть за один раз. Если мы способны обозреть пространство под углом 45 гр. вправо и влево по отношению к направлению просмотра (рис.6.22), то наше поле просмотра составит 90 градусов. Рис.6.22. Поле просмотра. Вообще, поле просмотра - это одно из ключевых понятий в технологии отсечения лучей. Поэтому мы должны определить, какое поле просмотра нам необходимо. Большинство животных имеет очень большое поле просмотра - 90 и более градусов. Правда, для нашего случая я выбрал его равным 60 гр. Просто мне нравится то, что получается при этом на экране. Вы сами можете задать любой угол, но постарайтесь, чтобы он попадал в диапазон между 60 и 90 градусами. Теперь мы знаем, что нам надо отсечь все лучи, которые не попадают в наше поле просмотра. Потом нам надо выяснить точки пересечения этих лучей со стенами и использовать информацию о каждом пересечении для построения трехмерного образа. Для примера посмотрим на рис. 6.23. - 202 - Рис.6.23.Простое отсечение лучей при поле просмотра в 60 градусов.